// Copyright 2006 PR1ME. All Rights Reserved.

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

public abstract class Cluster {

  public static Cluster create(String descriptor, CorpusFile[] files,
      String[] wordList, int[] wordFrequency) {

    // degenerate case
    if (files.length < 8) {
      return new FileCluster(descriptor, files);
    }

    List[] clusters = new List[7];
    Centroid[] centroids = new Centroid[7];

    // put each file into a random cluster to begin with
    for (int i = 0; i < 7; ++i) {
      clusters[i] = new ArrayList();
    }
    for (int i = 0; i < files.length; ++i) {
      clusters[i % 7].add(files[i]);
    }

    boolean didChange;
    do {
      // compute centroids
      for (int i = 0; i < 7; ++i) {
        centroids[i] = computeCentroid(clusters[i], wordList.length);
      }

      // create a new set of clusters
      List[] newClusters = new List[7];
      for (int i = 0; i < 7; ++i) {
        newClusters[i] = new ArrayList();
      }

      // sort each file into its proper cluster
      didChange = false;
      for (int i = 0; i < 7; ++i) {
        List curCluster = clusters[i];
        for (int j = 0; j < curCluster.size(); ++j) {
          CorpusFile file = (CorpusFile) curCluster.get(j);
          int newIndex = findNearestCentroid(file.getBitSet(), centroids);
          newClusters[newIndex].add(file);
          if (i != newIndex) {
            didChange = true;
          }
        }
      }

      // update the clusters with the new clusters
      clusters = newClusters;

    } while (didChange);

    List subClusters = new ArrayList();
    for (int i = 0; i < 7; ++i) {
      List curCluster = clusters[i];
      if (!curCluster.isEmpty()) {
        CorpusFile[] clusterFiles = (CorpusFile[]) curCluster.toArray(new CorpusFile[curCluster.size()]);
        String clusterDescriptor = centroids[i].computeDescriptor(wordList,
            wordFrequency);
        subClusters.add(create(clusterDescriptor, clusterFiles, wordList,
            wordFrequency));
      }
    }

    return new SuperCluster(descriptor,
        (Cluster[]) subClusters.toArray(new Cluster[subClusters.size()]));
  }

  private static Centroid computeCentroid(List files, int dimensions) {
    Centroid centroid = new Centroid(dimensions);
    for (int i = 0; i < files.size(); ++i) {
      CorpusFile file = (CorpusFile) files.get(i);
      centroid.add(file.getBitSet());
    }
    return centroid;
  }

  private static int findNearestCentroid(BitSet bitSet, Centroid[] centroids) {
    double best = Double.POSITIVE_INFINITY;
    int bestIndex = -1;
    for (int i = 0; i < centroids.length; ++i) {
      double result = centroids[i].distance(bitSet);
      if (result < best) {
        best = result;
        bestIndex = i;
      }
    }
    return bestIndex;
  }

  public Cluster(String descriptor) {
    this.descriptor = (descriptor == null) ? "{no description)" : descriptor;
  }

  public String getDescriptor() {
    return descriptor;
  }

  public abstract String[] getItems();
  public abstract SuperCluster isSuperCluster();
  private final String descriptor;

}
